package practice7;

import java.util.Arrays;

public class P5 {

	static int INF=(int)1e9;
	static int[] dist=new int[2022];		//�ýڵ㵽1�ڵ�ľ���
	static boolean[] st=new boolean[2022];	//�ýڵ��Ƿ���ʹ�
	static int[][] g=new int[2022][2022];	//�ٽӾ���
	//�����Լ��
	public static int gcd(int a,int b) {
		if(a%b==0) {
			return b;
		}
		return gcd(b,a%b);
	}
	//����С������
	public static int lcd(int a,int b) {
		return a*b/gcd(a,b);
	}
	//�����·��
	public static int dijkstra() {
		Arrays.fill(dist, INF);
		dist[1]=0;
		for(int i=0;i<2020;i++) {
			//�ҳ����������ĵ�
			int t=-1;
			for(int j=1;j<=2021;j++) {
				if(!st[j] && (t==-1 || dist[j]<dist[t])) {
					t=j;
				}
			}
			st[t]=true;
			//�������ھӵľ���
			for(int j=1;j<=2021;j++) {
				if(g[t][j]!=INF) {
					dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
				}
			}
		}
		if(dist[2021]==INF) {
			return -1;
		}
		return dist[2021];
	}
	
	
	public static void main(String[] args) {
		for(int i=0;i<g.length;i++) {
			Arrays.fill(g[i], INF);
		}

		//����ͼ
		for(int a=1;a<=2021;a++) {
			for(int b=a+1;b<=2021;b++) {
				if(Math.abs(a-b)>21) {
					continue;
				}
				g[a][b]=lcd(a,b);
				g[b][a]=lcd(a,b);
			}
		}
		int ans=dijkstra();
		System.out.println(ans);
		
	}

}
